Formulation
Vector Quantization (VQ) is a well known method to quantize a fixed dimensional random vector. (see A. Gersho and R. Gray, "Vector Quantization and Signal Compression", Kluwer Press, 1992). Vector Quantization is a block matching technique. Given an instance of the input random vector, a VQ encoder simply searches through a collection (a codebook) of predetermined vectors called codevectors that represents the random variable and selects one that best matches this instance. The selection is generally based on minimizing a predetermined measure of distortion between the instance and each codevector. The selected vector is referred to as the "quantized" representative of the input. The codebook may be designed off-line from a "training set" of vectors. The performance of a VQ scheme depends on how well the codebook represents the statistics of the source. This significantly depends on the training ratio or the ratio of the size of the training set to that of the codebook. Higher training ratios generally lead to better performance. Typically, VQ outperforms other methods including independent quantization of individual components of the random vector (scalar quantization). The improved performance of VQ may be attributed to its ability to exploit the redundancy between the components of the random vector.
In many signal compression applications, however, a signal evolving in time, may be well represented by a sequence of random vectors with a varying dimensionality L. Each such vector can often be modeled as consisting of a random subset of the components of an underlying, and possibly unobservable, A dimensional random vector, X. FIG. 1 illustrates a model of the generation of such a random vector, S, called a subvector, from the vector X by a sub-sampling operation. The random sub-sampler function, g(X) can be represented by a K dimensional random binary selector vector Q. The non-zero components of Q specify the components of X that are selected, i.e., sub-sampled. We assume that Q takes on one of N vector values. For example, if K=4, X=(x.sub.1,x.sub.2,x.sub.3,x.sub.4) and Q=(0,1,0,1), then S=g(X)=(x.sub.2,x.sub.4). Clearly, since Q is random, S is a variable dimensional quantity. Since the dimension of S, L, varies from one occurrence to another, conventional VQ is not useful since a fixed dimension codebook is not applicable here. Efficient quantization of the subvector S is a challenging problem. The problem is to find a digital code or binary word with a particular number of bits that can be generated by the encoder to represent any observed instance of S so that a suitably accurate reproduction of S can be regenerated by a decoder from observation of the digital code.
Previously Adoul and Delprat (J-P. Adoul and M. Delprat, "Design algorithm for variable-length vector quantizers," Proc. Allerton Conf. Circuits, Systems, Computers, pp. 1004-1011, October 1986.) have studied variable dimension VQ. However, in their formulation, a separate codebook is required for each possible dimension that the input vector might have. This method will require an extraordinarily large amount of memory to store a very large number of codebooks. Furthermore, the design of each of these codebooks requires an astronomic amount of training data that is entirely impractical for many applications. Our invention offers an entirely different solution that requires the storage of only a single codebook.
A related problem that is also solved by our invention is the digital compression of a large fixed dimension vector X of dimension K from observation of a L-dimension subvector S obtained from X by a sub-sampling operation with a variable selection of the number and location of indices identifying the components to be sampled.
Our formulation of variable dimensional vector quantization and the invention described herein to solve this problem has not been found in the prior art. However, the problem is relevant to some applications in speech coding and elsewhere and our invention results in considerable performance improvements in speech coding systems that we have tested.
An important extension of the VDVQ formulation is the design of a pattern classifier for variable dimensional vectors. No direct method can be found in prior art, some work has been done in speech recognition context using indirect methods such as Dynamic Time Warping (DTW) (see chapter 11 of "Discrete Time Processing of Speech Signals", by Proakis, et, al, MacMillan, 1993). Our invention offers a direct and efficient way to classify variable dimension feature vectors.